Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Huairui Chu and Bingkai Lin. FPT Approximation Using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chu_et_al:LIPIcs.ISAAC.2023.19, author = {Chu, Huairui and Lin, Bingkai}, title = {{FPT Approximation Using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {19:1--19:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.19}, URN = {urn:nbn:de:0030-drops-193216}, doi = {10.4230/LIPIcs.ISAAC.2023.19}, annote = {Keywords: FPT approximation algorithm, Treewidth, Capacitated vertex cover, Target set selection, Vector dominating set} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Bingkai Lin, Xuandi Ren, Yican Sun, and Xiuhan Wang. On Lower Bounds of Approximating Parameterized k-Clique. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 90:1-90:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lin_et_al:LIPIcs.ICALP.2022.90, author = {Lin, Bingkai and Ren, Xuandi and Sun, Yican and Wang, Xiuhan}, title = {{On Lower Bounds of Approximating Parameterized k-Clique}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {90:1--90:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.90}, URN = {urn:nbn:de:0030-drops-164317}, doi = {10.4230/LIPIcs.ICALP.2022.90}, annote = {Keywords: parameterized complexity, k-clique, hardness of approximation} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Bingkai Lin. A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 81:1-81:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{lin:LIPIcs.ICALP.2019.81, author = {Lin, Bingkai}, title = {{A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {81:1--81:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.81}, URN = {urn:nbn:de:0030-drops-106573}, doi = {10.4230/LIPIcs.ICALP.2019.81}, annote = {Keywords: set cover, FPT inapproximability, gap-producing reduction, (n, k)-universal set} }
Feedback for Dagstuhl Publishing